/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/

#include<iostream>
using namespace std;



template<class DataType>
struct Node{
    DataType data;
    Node* next;
};

template<class DataType>
class LinkQueue{
    public:
        LinkQueue();
        LinkQueue(DataType a[], int n);
        ~LinkQueue();
        void EnQueue(DataType x);
        DataType DeQueue();
        DataType GetHead();
        bool Empty();

        void PrintQueue();
    private:
        Node<DataType> *front, *rear;
};


template<class DataType>
LinkQueue<DataType> :: LinkQueue(){
    Node<DataType> *s;
    s = new Node<DataType>;
    s->next = nullptr;
    front = rear = s;
}

template<class DataType>
LinkQueue<DataType> :: LinkQueue(DataType a[], int n){
    Node<DataType> *s;
    s = new Node<DataType>;
    front = new Node<DataType>;
    s->data = a[0];
    s->next = nullptr;
    rear = s;
    front->next = s;
    for(int i=1; i<n; i++){
        s = new Node<DataType>;
        s->data = a[i];
        s->next = nullptr;
        rear->next = s;
        rear = s;
    }
}

template<class DataType>
LinkQueue<DataType> :: ~LinkQueue(){
    Node<DataType> *p=front, *s;
    while(p->next != nullptr){
        s = p;
        p = p->next;
        delete s;
    }
}

template<class DataType>
void LinkQueue<DataType> :: EnQueue(DataType x){
    Node<DataType> *s;
    s = new Node<DataType>;
    s->data = x;
    s->next = nullptr;

    rear->next = s;
    rear = s;
}

template<class DataType>
DataType LinkQueue<DataType> :: DeQueue(){
    DataType value = front->next->data;
    Node<DataType> *p = front;
    front = front->next;
    delete p;
    return value;
}

template<class DataType>
DataType LinkQueue<DataType> :: GetHead(){
    return front->next->data;
}

template<class DataType>
bool LinkQueue<DataType> :: Empty(){
    if(front->next == nullptr) return true;
    else return false;
}


template<class DataType>
void LinkQueue<DataType> :: PrintQueue(){
    Node<DataType> *p = front;
    while(p->next != nullptr){
        p = p->next;
        cout << p->data << "\t";
    }
    cout << endl;
}

int main(){
    int a[5] = {1,2,3,4,5};
    LinkQueue<int> Q(a,5);
    
    cout << "当前链队列内容为：";
    Q.PrintQueue();

    cout << "从中取出队首元素：" << Q.DeQueue() << endl;
    cout << "当前链队列内容为：";
    Q.PrintQueue();

    cout << "将元素10入队：";
    Q.EnQueue(10);
    cout << "当前链队列内容为：";
    Q.PrintQueue();

    cout << "获取队首元素：" << Q.GetHead() << endl;

    int test;
    cin >> test;
}